template<typename T, class VST>
void travIn_R(BinNodePosi(T) x, VST &visit) {
	if(!x) return;
	travPre_R(x->lc, visit);
	visit(x->data);
	travPre_R(x->rc, visit);
}

template<typename T, class VST>
static void goAlongLeftBranch(BinNodePosi(T) x, VST &visit, std::stack<BinNodePosi(T)> &s) {
	while(x) {
		s.push(x);
		x = x->lc;
	}
}

template <typename T, class VST>
void travIn_I1(BinNodePosi(T) x, VST &visit) {
	std::stack<BinNodePosi(T)> s;
	while(true) {
		goAlongLeftBranch(x, visit, s);
		if(s.empty()) return;
		
		x = s.top();
		s.pop();

		visit(x->data);
		x = x->rc;
	}
}

template <typename T, class VST>
void travIn_I2(BinNodePosi(T) x, VST &visit) {
	std::stack<BinNodePosi(T) > s;
	while(true) {
		if(x) {
			s.push(x);
			x = x->lc;
		}
		else if(!s.empty()) {
			x = s.top();
			s.pop();

			visit(x->data);
			x = x->rc;
		}
		else {
			return;
		}
	}
}

template <class T, class VST>
void travIn_I3(BinNodePosi(T) x, VST &visit) {
	if(!x) return;
	bool backtrack = false;
	while(true) {
		if(!backtrack && HasLChild(*x)) {
			x = x->lc;
		}
		else {
			visit(x->data);
			if(HasRChild(*x)) {
				x = x->rc;
				backtrack = false;
			}
			else {
				// reach the most right node
				// let backtrack = true
				// jump to the successor
				if(!(x = x->succ())) break;
				backtrack = true;
			}
		}
	}
}